package com.lin.mergetwolists;


//  Definition for singly-linked list.

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * @author 九分石人
 */
public class MergeTwoLists {

    /**
     * 将l2插入l1
     *
     * @param l1 链表l1
     * @param l2 链表l2
     * @return 新链表头节点
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = l1;
        while (l2 != null) {
            while (l1 != null) {
                if (l2 != null) {
                    if (l2.val >= l1.val && l1.next == null) {
                        ListNode val = l2;
                        l1.next = val;
                        l2 = l2.next;
                        val.next = null;
                        break;
                    } else if (l2.val >= l1.val && l2.val <= l1.next.val) {
                        ListNode val = l2;
                        ListNode ll = l1.next;
                        l1.next = val;
                        l2 = l2.next;
                        val.next = ll;
                        break;
                    } else if (l2.val < l1.val) {
                        ListNode val = l2;
                        head = val;
                        l2 = l2.next;
                        val.next = l1;
                        break;
                    } else {
                        l1 = l1.next;
                    }
                }
            }
            l1 = head;
            if (l2 == null) {
                break;
            }
        }
        return head;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(-9);
        ListNode l2 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
        l1.next = l2;
//        l2.next = l4;
        ListNode r1 = new ListNode(5);
        ListNode r3 = new ListNode(7);
//        ListNode r4 = new ListNode(4);
        r1.next = r3;
//        r3.next = r4;
        ListNode listNode = mergeTwoLists(l1, r1);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}